package com.ufo.exercise;

import java.util.Stack;

/**
 * Dijkstra双栈算术表达式求值
 * 前提假设没有省略的括号，即所有运算优先级仅由括号控制
 * 用一个栈保存数字、另一个栈保存运算符
 * 忽略左括号，遇到右括号时，弹出操作符和相应数量运算数，执行运算，结果压回运算数的栈
 * */
public class Evaluate {
    public static void main(String[] args){
        double r1=parseV1("( ( 10 + 2 ) * ( ( 3 - 2 ) / 1 ) )");
        assert r1==12;
        System.out.println("r1="+r1);
    }
    /* 版本1 加减乘除 */
    public static double parseV1(String expression){
        double sum=0;
        String[] items=expression.split(" ");
        Stack<String> stackOfOperations=new Stack<>();
        Stack<Double> stackOfNumbers=new Stack<>();

        for(String item: items){
            switch (item){
                case "+":
                case "-":
                case "*":
                case "/":stackOfOperations.push(item);break;
                case "(":break;//nothing
                case ")":
                    String op=stackOfOperations.pop();
                    Double n1=stackOfNumbers.pop(),
                        n2=stackOfNumbers.pop();
                    switch (op){
                        case "+":sum=n2+n1;break;
                        case "-":sum=n2-n1;break;
                        case "*":sum=n2*n1;break;
                        case "/":sum=n2/n1;
                    }
                    stackOfNumbers.push(sum);
                    break;
                default: stackOfNumbers.push(Double.parseDouble(item));
            }
        }

        return sum;
    }
}
